1. Field of the Invention
This invention relates generally to crosspoint switches and more specifically to arrays of single-sided crosspoint switching elements with distributed control, particularly such arrays which can be modularly increased in size and are fault tolerant.
2. Prior Art
There is a need for very large switching systems, i.e., systems with hundreds or even thousands or ports, that can be used, for example, to interconnect processors to memories in highly parallel machines or processors to their peripheral devices in computer system I/O configurations.
Various high-performance switching fabrics have been described in the prior art for use as switching systems for computer applications. Distributed control of a crosspoint switch is described by L. D. Amdahl et al. in U.S. Pat. No. 3,226,688, entitled "MODULAR COMPUTER SYSTEM". It is also described by P. A. Franaszek in U.S. Pat. No. 4,752,777, entitled "DELTA NETWORK OF A CROSS-POINT SWITCH", and in U.S. Pat. No. 4,814,762, entitled "DELTA NETWORK CONTROL OF A CROSS-POINT SWITCH." However, all these patents describe two-sided crosspoint switches. One-sided crosspoint switches are inherently more complicated to control, since they have twice the number of crosspoint elements for a particular number of ports and also have internal busses (unlike two-sided crosspoint switches). Each interconnection of two ports through a one-sided crosspoint switch requires the setting of two crosspoint elements and there are numerous possibilities for each interconnection (one for each internal bus). All this makes one-sided crosspoint switches inherently much more flexible, but at the same time makes one-sided crosspoint switches more expensive and more difficult and unobvious how best to control, especially if distributed control is desired.
An important consideration for the design of very large switching systems is the performance of the controller. A switch with a single controller can service a large number of requests by using parallel pipeline techniques, as described by C. J. Georgiou in U.S. Pat. No. 4,630,045, entitled "CONTROLLER FOR A CROSS-POINT SWITCHING MATRIX." But as the size of the switching matrix grows, the worst-case waiting time for servicing requests also grows linearly with the number of ports, and may become unacceptably long.
For example, in a 60-port switch with a single controller, such as the IBM ESCON Director switching system described in the paper "The ESCON Director: A Dynamic Switch for 200 Mb/s Fiber-Optic Links," by C. J. Georgiou, et al, IBM Journal of Research and Development (October 1991), the worst-case waiting time is of the order of 12 microseconds. This is not significant in the current I/O environment that assumes a network with a 3 kilometer radius, because the signal propagation delay in the optical fibers (5 microseconds/kilometer) would dominate the network delay (i.e., 30 microseconds for a 3 kilometer round-trip transmission). But if the size of the switching system were to grow to 1000 ports, the worst-case waiting delay could become 220 microseconds, which would seriously affect system performance.
In U.S. Pat. No. 4,605,928, entitled "FAULT-TOLERANT ARRAY OF CROSS-POINT SWITCHING MATRICES", C. J. Georgiou describes a one-sided crosspoint matrix switch that is used to provide fault-tolerance and expandability to the switching system, but only one controller is used. In U.S. Pat. No. 4,929,940, entitled "COLLISION CROSSBAR SWITCH", Franaszek et al. describe a self-routing crosspoint matrix switch which avoids the need for determining in advance whether the desired output port is available for connection or is already connected to another port. This facilitates distribution of crosspoint control throughout the switching system, but what is specifically described is a two-sided crosspoint switch rather than a one-sided crosspoint switch. Furthermore, if too many collisions occur, performance of the switch suffers. It is not clear that in a situation where controller performance is a limiting factor (and especially in the case of a one-sided crosspoint switch) that collision frequency will not be unacceptable.
In a co-pending patent application, Ser. No. 429,674, U.S. Pat. No. 5,072,217, entitled "ONE-SIDED CROSSPOINT SWITCH WITH DISTRIBUTED CONTROL", by C. J. Georgiou and A. Varma, a switching system is described that uses multiple controllers to reduce the worst-case waiting time. A distinct group of internal busses is associated with each controller, which also controls all of the crosspoint switching elements connected to the group of busses associated with that controller. However, port status information is shared and commonly accessed, which may become a bottleneck point in large switching configurations, even if the port status information is distributed in some way among the controllers, which may significantly affect the overall system performance. Furthermore, interconnection possibilities are distributed among the controllers for handling responsibility. As a consequence, each controller must monitor all of the connection requests in order to determine which ones are to be handled by that controller. As the size of the switch gets ever larger, this monitoring task becomes impractical to implement with efficiency and turns into a bottleneck function.
Another major consideration in computer input/output (I/O) switch design is upgradability. For example, a user may initially want to install a 250-port switching system which, later, may need to be upgraded to 1000 ports. It would be advantageous to have a switch that could be readily field-upgraded to higher capacity. Similarly, it would be very advantageous for the switch manufacturer to have a design that could be easily mapped to switches of various sizes. In the aforementioned co-pending patent application, some modularity is apparent, but it is not clear that an additional column of crosspoint chips could be added easily, for example, without adding an additional controller or doing some rewiring, or that the failure of a controller will not also result in the loss of all of the internal busses controlled entirely by that failed controller.